package leetcode.pre100;

import leetcode.top100.Code03_LongestUnRepeatString;
import leetcode.top100.Code438_字母异位词;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
 * <p>
 * 示例：
 * <p>
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 * 说明：
 * <p>
 * 如果 S 中不存这样的子串，则返回空字符串 ""。
 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 滑动窗口类似见
 * {@link Code03_LongestUnRepeatString}
 * {@link Code438_字母异位词}
 *
 * @date 2020/4/6 19:59
 */
public class Code76_MinCoveredSubString_最小覆盖子串 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(new Code76_MinCoveredSubString_最小覆盖子串().minWindow2(s, t));
    }
    /**
     * 方式1：遍历所有s的子串，每一个进行判断。
     * 时间O(s²t)
     */
    public String minWindow1(String s, String t) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(satisfy(s.substring(i,j+1),t)){
                    if(res.equals("") || j - i + 1 < res.length())
                        res = s.substring(i,j+1);
                }
            }
        }
        return res;
    }
    //判断s中是否含有t的所有。用hash.
    // s可能是aab  t可能是aa
    public boolean satisfy(String s,String t){
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int count = map.getOrDefault(c,0);
            map.put(c,count+1);
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            //如果没有，直接返回
            if(!map.containsKey(c)) return false;
            //譬如s = a ，t = aa。那么第二个a时count= 0不足
            int count = map.get(c);
            if(count == 0) return false;
            map.put(c,count-1);
        }
        return true;
    }
    /**
     * 方式2：滑动窗口。   如  s = ababcq   t = bc
     * 基于这样一种机制：left，right为窗口边界。
     * 1)left = right = 0;
     * 2) right++,直到满足滑动窗口内的subString 包含t所有字符。  subString = ababc
     * 3) 优化滑动窗口，直到窗口最小，且满足滑动窗口内的subString 包含t所有字符。 subString=bc
     * 4)left++，转2.
     *
     * 总的时间复杂度是O(t + 2s)
     */
    public String minWindow2(String s, String t) {
        if(s == null || t == null || s.length() < t.length()) return "";
        //使用两个map分别装t和滑动窗口内的字符
        Map<Character,Integer> tMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0)+1);
        }
        //设置一个量，表示出现的不同字符种类
        int formed = 0;
        int required = tMap.size();
        Map<Character,Integer> winMap = new HashMap<>();
        int left = 0;
        int right = 0;
        String res = "";
        while (right < s.length()){ //俩while最多执行 2s.length 次 left++,right++总有一个执行
            char c = s.charAt(right);
            //winMap更新字符个数
            winMap.put(c,winMap.getOrDefault(c,0)+1);
            //如果tmap包含c，并且tamp中c的个数和winmap中c的个数一样，
            // 那么说明有一个字符已经统计完了
            if(tMap.containsKey(c) && winMap.get(c).equals(tMap.get(c))){
                formed++;
            }
            //如果该窗口内都已经统计完了，那么优化窗口为最小
            while (left <= right && formed == required){
                //看left
                c = s.charAt(left);
                //如果是第一次，或者有更优解
                if(res.equals("") || right - left + 1 < res.length()){
                    res = s.substring(left,right+1);
                }
                //window移除left
                winMap.put(c,winMap.get(c)-1);
                //如果已经不满足s包含所有的t
                if(tMap.containsKey(c) && winMap.get(c) < tMap.get(c)){
                    formed--;
                }
                left++;
            }
            right++;
        }
        return res;
    }
}
